/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2024-07-30
 * Time: 20:11
 */
class Solution24 {
    public int integerReplacement(int n) {
        int ret = 0;
        while(n > 1) {
            // 如果是偶数 只能/2
            if(n % 2 == 0) {
                n /= 2;
                ret++;
            }else {
                // 特殊讨论
                if(n == 3) {
                    ret += 2;
                    n = 1;
                }
                else if(n % 4 == 1) {
                    n /= 2;
                    ret += 2;
                }else {
                    n = n / 2 + 1;
                    ret += 2;
                }
            }
        }
        return ret;
    }
}


//解法一：记忆化搜索
//class Solution {
//    // 加上备忘录
//    Map<Long,Integer> hash;
//    public int integerReplacement(int n) {
//        hash = new HashMap<>();
//        return dfs(n * 1L);
//    }
//
//    int dfs(long n) {
//
//        if(hash.containsKey(n)) {
//            return hash.get(n);
//        }
//        if(n == 1) {
//            hash.put(n,0);
//            return hash.get(n);
//        }
//        if(n % 2 == 0) {
//            hash.put(n,1+dfs(n/2));
//            return hash.get(n);
//        }else {
//            hash.put(n,1+Math.min(dfs(n-1),dfs(n+1)));
//            return hash.get(n);
//        }
//    }
//}
